
/****************************************************************************/
/*Copyright (c) 2011, Florent DEVILLE.                                      */
/*All rights reserved.                                                      */
/*                                                                          */
/*Redistribution and use in source and binary forms, with or without        */
/*modification, are permitted provided that the following conditions        */
/*are met:                                                                  */
/*                                                                          */
/* - Redistributions of source code must retain the above copyright         */
/*notice, this list of conditions and the following disclaimer.             */
/* - Redistributions in binary form must reproduce the above                */
/*copyright notice, this list of conditions and the following               */
/*disclaimer in the documentation and/or other materials provided           */
/*with the distribution.                                                    */
/* - The names of its contributors cannot be used to endorse or promote     */
/*products derived from this software without specific prior written        */
/*permission.                                                               */
/* - The source code cannot be used for commercial purposes without         */ 
/*its contributors' permission.                                             */
/*                                                                          */
/*THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       */
/*"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT         */
/*LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS         */
/*FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE            */
/*COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,       */
/*INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,      */
/*BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;          */
/*LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER          */
/*CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT        */
/*LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN         */
/*ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE           */
/*POSSIBILITY OF SUCH DAMAGE.                                               */
/****************************************************************************/

#include "RTPerlinNoise.h"
#include "RTInterpolation.h"

#include <math.h>

namespace RT
{

	const I32 RTPerlinNoise::permutation[] = { 151,160,137,91,90,15,
	   131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
	   190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
	   88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
	   77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
	   102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
	   135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
	   5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
	   223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
	   129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
	   251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
	   49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
	   138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
	   };

	const I32 RTPerlinNoise::p[] = { 151,160,137,91,90,15,
	   131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
	   190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
	   88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
	   77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
	   102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
	   135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
	   5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
	   223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
	   129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
	   251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
	   49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
	   138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180,
	   151,160,137,91,90,15,
	   131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
	   190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
	   88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
	   77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
	   102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
	   135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
	   5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
	   223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
	   129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
	   251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
	   49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
	   138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
	   };

	/*Calculate the fade*/
	F64 RTPerlinNoise::fade(F64 t) 
	{ 
		return t * t * t * (t * (t * 6 - 15) + 10); 
	}

	/*Calculate gradient*/
	F64 RTPerlinNoise::grad(I32 hash, F64 x, F64 y, F64 z) 
	{
		  I32 h = hash & 15;                      // CONVERT LO 4 BITS OF HASH CODE
		  F64 u = h<8 ? x : y,                 // INTO 12 GRADIENT DIRECTIONS.
				 v = h<4 ? y : h==12||h==14 ? x : z;
		  return ((h&1) == 0 ? u : -u) + ((h&2) == 0 ? v : -v);
	}

	/*Calculate a linear interpolation between a and b*/
	F64 RTPerlinNoise::lerp(F64 t, F64 a, F64 b)
	{
		return (F64)RTInterpolation::linearInterpolation((F32)a, (F32)b, (F32)t);
	}

	/*Return a noise*/
	F64 RTPerlinNoise::noise(F64 x, F64 y, F64 z) 
	{
		I32 X = (I32)floor(x) & 255;                  // FIND UNIT CUBE THAT
		I32 Y = (I32)floor(y) & 255;                  // CONTAINS POINT.
		I32 Z = (I32)floor(z) & 255;
		x -= floor(x);                                // FIND RELATIVE X,Y,Z
		y -= floor(y);                                // OF POINT IN CUBE.
		z -= floor(z);

		F64 u = fade(x);                                // COMPUTE FADE CURVES
		F64 v = fade(y);                                // FOR EACH OF X,Y,Z.
		F64 w = fade(z);

		I32 A = p[X  ]+Y; 
		I32  AA = p[A]+Z; 
		I32  AB = p[A+1]+Z;      // HASH COORDINATES OF
		I32  B = p[X+1]+Y;
		I32  BA = p[B]+Z; 
		I32  BB = p[B+1]+Z;      // THE 8 CUBE CORNERS,


		return lerp(w, lerp(v, lerp(u, grad(p[AA  ], x  , y  , z   ),  // AND ADD
										 grad(p[BA  ], x-1, y  , z   )), // BLENDED
								 lerp(u, grad(p[AB  ], x  , y-1, z   ),  // RESULTS
										 grad(p[BB  ], x-1, y-1, z   ))),// FROM  8
						 lerp(v, lerp(u, grad(p[AA+1], x  , y  , z-1 ),  // CORNERS
										 grad(p[BA+1], x-1, y  , z-1 )), // OF CUBE
								 lerp(u, grad(p[AB+1], x  , y-1, z-1 ),
										 grad(p[BB+1], x-1, y-1, z-1 ))));
	}

	/*Return a perlin noise*/
	F32 RTPerlinNoise::perlin(const RTVector3f& p, F32 persistance, I32 octave)
	{
		F32 amplitude = 1;
		F32 frequency = 1;

		F64 perlin = 0;

		for(I32 i = 0; i < octave; i++)
		{
			perlin += noise(p.x * frequency, p.y * frequency, p.z * frequency) * amplitude;
			amplitude *= persistance;
			frequency *= 2;
		}

		return (F32)perlin;
	}
}